public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().findTargetSumWays(new int[]{1,1,1,1,1}, 3));
        System.out.println(new Solution().findTargetSumWays(new int[]{1}, 1));
    }
}


class Solution {
    int min = -1000;
    int max = 1000;


    int getVal(int[] dp, int key) {
        if (key > max || key < min) {
            return 0;
        }
        return dp[key + 1000];
    }

    void setVal(int[] dp, int key, int val) {
        dp[key + 1000] = val;
    }

    public int findTargetSumWays(int[] nums, int target) {
        int[] dp = new int[2001];
        int[] prevDp = new int[2001];
        setVal(prevDp, 0, 1);
        for (int num : nums) {
            for (int i = min; i <= max; i++) {
                setVal(dp, i, getVal(prevDp, i - num) + getVal(prevDp, i + num));
            }
            prevDp = dp;
            dp = new int[2001];
        }
        return getVal(prevDp, target);
    }
}